package com.mgq.algorithm;

import java.util.*;


/**
 * @author MaGuangQi
 * @description leetcode 169题 https://leetcode-cn.com/problems/majority-element/
 * 输入: [3,2,3]
 * 输出: 3
 * <p>
 * 输入: [2,2,1,1,1,2,2]
 * 输出: 2
 * @date 2020-07-03 21:34
 **/
public class MajorityEle {
    /**
     * 解法一: 使用暴力解法 时间复杂度O(N^2)
     * 双重for循环
     */
    public int majorityElement(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int count = 1;
            for (int j = 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    count++;
                }
                if (count > nums.length / 2) {
                    return nums[i];
                }
            }
        }
        return nums[0];
    }

    /**
     * 解法二:使用Map
     * 只要有计算的题目,我们就应该想到使用map
     */
    public int majorityElement2(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums) {
            Integer count = countMap.get(num);
            if (count == null) {
                countMap.put(num, 1);
            } else {
                count++;
                countMap.put(num, count);
            }
        }
        Map.Entry<Integer, Integer> majorEntry = null;
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            if (majorEntry == null || entry.getValue() > majorEntry.getValue()) {
                majorEntry = entry;
            }
        }
        assert majorEntry != null;
        return majorEntry.getKey();
    }

    /**
     * 解法三:使用排序
     * 因为题目说必定会有一个元素的个数大于n/2
     * 因此我们排序,取中间的值,一定次数最多的
     * 时间复杂度O(NlogN) 排序的平均复杂度
     */
    public int majorityElement3(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    /**
     * 解法四:使用分治的思想
     * 一分为二,左边求个数最大的元素,右边也求个数最大的元素
     * 3种情况
     * 1. left=right 左边和右边个数最大的元素相等,肯定是left或者right
     * 2. left=right 左边和右边个数最大的元素大于,肯定是left
     * 1. left=right 左边和右边个数最大的元素小于,肯定是right
     */
    public int majorityElement4(int[] nums) {
        return majority(nums, 0, nums.length - 1);
    }

    public int majority(int[] nums, int low, int high) {
        //如果low和high相当,直接返回
        if (low == high) {
            return nums[low];
        }
        //拆分,计算中间下标
        int mid = (high - low) / 2 + low;
        int left = majority(nums, low, mid);
        int right = majority(nums, mid + 1, high);
        //如果两个数返回的数一样,说明他们就是众数
        if (left == right) {
            return left;
        }
        //如果不一样,就得统计他们2个的次数,谁最多谁就是众数
        int countLeft = countInRange(nums, left, low, high);
        int countRight = countInRange(nums, right, low, high);
        return countLeft > countRight ? left : right;
    }

    /**
     * 在数组中某个统计元素出现的个数
     */
    public int countInRange(int[] nums, int num, int low, int higt) {
        int count = 0;
        for (int i = low; i <= higt; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    /**
     * 解法五,使用投票的方法
     * 如果我们把众数记为 +1，把其他数记为 -1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多
     * 投票算法证明
     * 如果候选人不是maj 则 maj,会和其他非候选人一起反对 会反对候选人,所以候选人一定会下台(maj==0时发生换届选举)
     * 如果候选人是maj , 则maj 会支持自己，其他候选人会反对，同样因为maj 票数超过一半，所以maj 一定会成功当选
     *
     * [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
     *
     * 说明: 相当于现实中投票,一开始7投自己,接下来再得一票, 然后是5投一票,把7抵消一票,7再投一票
     * 最终票数最多的会当选
     */
    public int majorElement(int[] nums) {
        int count = 0;
        Integer candidate = null;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            int s = num == candidate ? 1 : -1;
            count = count + s;
        }
        return candidate;
    }

    public static void main(String[] args) {
        MajorityEle majorityEle = new MajorityEle();
        int[] i = new int[]{3, 2, 3};
        int[] h = new int[]{1};
        int[] j = new int[]{2, 2, 1, 1, 1, 2, 2};
        int[] l = new int[]{8, 8, 7, 7, 7};


        System.out.println(majorityEle.majorityElement4(i));
        System.out.println(majorityEle.majorityElement4(j));
        System.out.println(majorityEle.majorityElement4(h));
        System.out.println(majorityEle.majorityElement4(l));
    }
}
